#
# @lc app=leetcode.cn id=528 lang=python3
#
# [528] 按权重随机选择
#

# @lc code=start
class Solution:

    def __init__(self, w: List[int]):
        for i in range(1, len(w)):
            w[i] += w[i - 1]
        self.w = w
        self.limit = w[-1]

    def pickIndex(self) -> int:
        return self.__bs(random.randint(1, self.limit))

    def __bs(self, k) -> int:
        L, R = 0, len(self.w)
        while L < R:
            m = (L + R) // 2
            if (k > self.w[m]):
                L = m + 1
            else:
                R = m
        return L

# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()
# @lc code=end
